//
// Created by Senhai Xu on 2025/3/5.
//
#include  <iostream>;
//01 链表

//单链表
//class Node{
//    public:
//        int data;
//    Node* next;
//    //构造函数
//    Node(int val): data(val), next(nullptr){}
//};
//class Linked_list{
//private:
//    Node* head;
//public:
//    // 构造函数   创建头结点 head是一个指针 应该初始化为一个指针值 而New返回的即为一个指向Node的指针
//    Linked_list(): head(new Node(-1)){};
//    //析构函数 释放所有节点内存
//    ~Linked_list(){
//    //在析构函数中释放头结点及链表其他节点的内存
//    while(head){
//        Node* temp = head;
//        head = head->next;
//        delete temp;
//    }
//    }
//    //头插法
//    void insert_head(int val){
//    Node* new_node = new Node(val);    //创建新节点
//    new_node->next = head->next; //新节点的next指向头结点的下一个节点
//    head->next = new_node; //头结点的next指向新节点
//    }
//    //尾插法
//    void insert_tail(int val){
//        Node* new_node = new Node(val);//创建新节点
//        Node* cur = head;//创建一个指针指向头结点
//        //遍历链表，找到最后一个节点
//        while(cur->next){
//            cur = cur->next;
//        }
//        //将新节点插入到链表的尾部
//        cur->next = new_node;
//    }
//    //批量插入
//    void insert_batch(int* arr, int size){
//        for(int i = 0; i < size; i++){
//            insert_tail(arr[i]);
//            std::cout<<"insert "<<arr[i]<<" success"<<std::endl;
//        }
//    }
//    //遍历链表并输出节点数据
//    void display(){
//        Node* cur = head->next;
//        while(cur){
//            std::cout<<cur->data<<" ";
//            cur = cur->next;
//        }
//    }
//
//};

//改造为模板类
// 模板化的 Node 类
template <typename T>
class Node {
public:
    T data;
    Node* next;
    // 构造函数
    Node(T val) : data(val), next(nullptr) {}
};
// 模板化的 Linked_list 类
template <typename T>
class Linked_list {
private:
    Node<T>* head;
public:
    // 构造函数   创建头结点 head 是一个指针 应该初始化为一个指针值 而 new 返回的即为一个指向 Node 的指针
//    T() 是一个值初始化表达式，它会创建一个 T 类型的临时对象，并将其初始化为该类型的默认值
    Linked_list() : head(new Node<T>(T())) {};

    // 析构函数 释放所有节点内存
    ~Linked_list() {
        // 在析构函数中释放头结点及链表其他节点的内存
        while (head) {
            Node<T>* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // 头插法
    void insert_head(T val) {
        Node<T>* new_node = new Node<T>(val);    // 创建新节点
        new_node->next = head->next; // 新节点的 next 指向头结点的下一个节点
        head->next = new_node; // 头结点的 next 指向新节点
    }

    // 尾插法
    void insert_tail(T val) {
        Node<T>* new_node = new Node<T>(val); // 创建新节点
        Node<T>* cur = head; // 创建一个指针指向头结点
        // 遍历链表，找到最后一个节点
        while (cur->next) {
            cur = cur->next;
        }
        // 将新节点插入到链表的尾部
        cur->next = new_node;
    }

    // 批量插入
    void insert_batch(T* arr, int size) {
        for (int i = 0; i < size; i++) {
            insert_tail(arr[i]);
            std::cout << "insert " << arr[i] << " success" << std::endl;
        }
    }

    // 遍历链表并输出节点数据
    void display() {
        Node<T>* cur = head->next;
        while (cur) {
            std::cout << cur->data << " ";
            cur = cur->next;
        }
        std::cout << std::endl;
    }
};

// 改造为双向链表
//双向链表需要定义头尾指针，同时在头插法和尾插法时需要注意节点的指向。
//循环链表只需要头指针，头插法时需要将head的next的prev指向新节点，尾插法时需要将head的prev的next指向新节点

//哈希表
//堆
//并查集
//B树
//B+树

